COMMENT ⊗   VALID 00002 PAGES 
RECORD PAGE   DESCRIPTION
 00001 00001
 00002 00002	\\M0BDR25\M1BDJ25\M2SUB\M3NGB25\M4XMAS25\.
 00021 ENDMK
⊗;
\\M0BDR25;\M1BDJ25;\M2SUB;\M3NGB25;\M4XMAS25;\.
\F0\CRECURSION



\J	The  term recursion  refers to  several  related concepts  in
computer science and mathematics.\.

Recursion relation

\J One or more functions of an integer  variable is defined by giving
initial values  and by giving the value  for larger integers in terms
of smaller ones.  No  single definition is generally accepted, so  we
shall give examples of increasing complexity.\.

	1. The Fibonacci sequence is given by the equations

        \F1f\F20\F1 = 1

        f\F21\F1 = 1

        f\F2n+1\F1 = f\F2n\F1 + f\F2n-1.\F0

\J	2. When differential equations are to be solved numerically,
recursion relations such as\.

     \F1f(x\F20\F1 + nh) = F(f(x\F20\F1 + (n-1)h) , f(x\F20\F1 + (n-2)h) , . . . , f(x\F20\F1 + (n-k)h))\F0


arise where \F1f\F0  is in general a vector of real numbers.

\J	3. When linear differential equations are solved by series, recursion
relations for the coefficients of the powers of the independent variables arise.\.

Recursive functions

\J	The systematic study of recursion began in the 1920's when mathematical
logic began to treat questions of definability, computability and decidability.
An important role is played by primitive recursive functions defined as
follows:\.

	a. Integer constants are primitive recursive.

\J	b. \F1x\F2i\F0 is a primitive recursive function of a set of arguments including
\F1x\F2i\F0.\.

	c. Addition and multiplication are primitive recursive.

\J	d. Functions obtained from primitiver recursive functions by composition
are primitive recursive.\.

\J	e. If\F1g\F0 and \F1h\F0 are primitive recursive functions of \F1n-1 \F0and \F1n+1\F0 arguments
respectively, and \F1f\F0 is defined by the relations\.

        \F1f(0 , x\F22\F1 , . . . , x\F2k\F1 = g(x\F22\F1 , . . . , x\F2k\F1)

	f(x\F21\F1 + 1, x\F22\F1 , . . . ,  \F2k\F1) = h(f(x\F21\F1 , . . . , x\F2k\F1) , . . . , x\F2n\F1n) ,\F0

then \F1f\F0 is primitive recursive.

\J	g. A function is primitive recursive only if it follows from the previous
rules that it is.\.

\J	All the common functions of number theory are primitive recursive.
Moreover, many important functions on other countable domains than the
integers correspond to primitive recursive functions when we choose a specific
enumeration for the domain.\.

\J	Primitive recursive functions are a proper subset of general recursive
functions.  The definition of general recursive function is like that given above
for primitive recursive functions except that the relations  \F4E\F0  are replaced
by an arbitrary finite collection of equations relating the values of \F1f\F0
for different arguments, and the function is considered defined \F3if and only
if\F0 a unique value of \F1f(x\F21\F1 , . . . , x\F2n\F1)\F0 can be deduced from the equations for
each \F1n\F0-tuplet \F1(x\F21\F1 , . . . , x\F2n\F1)\F0.  Naturally, if someone gives you an arbitrary
collection of such relations, you may not be able to determine whether
\F1f(x\F21\F1 , . . . , x\F2n\F1)\F0 is uniquely determined, so you may not know whether you have
a general recursive function or not.  This difficulty is unavoidable.  There is
no  way to give a definition scheme that is always guaranteed to give a function
but which will give all computable functions.
This fact is itself expressed in recursive function theory by the statement
that the set of computable functions is recursively enumerable but not
recursive.  It was first proved by Turing.\.

\J	An important result for computer science is that the general recursive
functions co-incide with the functions defined by Turing machines which are
a simple form of computer.  They also co-incide with the functions of
integers defined by Algol or Fortran programs assuming that the program can
cope with whatever size integers arise.\.

\J	The study of computable functions is the domain of recursive function
theory, an active branch of mathematics.  The connection between current research
in recursive function theory and computing practice or even current research
in computer science is rather tenuous.  This situation might change because
of developments in either field.\.


Recursive procedures

\J	In programming, it is frequently convenient to have a procedure use
itself as a subprocedure.  If the procedure does this, it is called recursive.
As far as programming languages are concerned, recursive procedures are quite
natural; it requires a special statement in the definition of the language
to forbid them.  However, implementing them requires that a special kind
of object code be compiled, and early programming languages like FORTRAN
don't do it.  The problem is that variables in the program correspond to
locations in the machine, and when the program is called by itself, it
will use these same locations forgetting their previous contents.
Therefore, recursive programs use an array called the stack to store the
contents of registers that must be saved.  This storage can
be done by the calling routine before it enters the subroutine or it can
be done by the subroutine before it uses the registers, the latter being
more common.  After the registers have been saved on the stack, the index
into the stack is increased by the number of registers stored so that
subsequent saving on the stack will have a fresh place.  When the subroutine
exits the contents of the saved registers are restored from the stack to
their previous values  and the stack pointer
is reduced by the amount it was previously increased.
This is done by the caller or by the subroutine
according to whether the caller or subroutine did the original storing.
An alternative technique is to use the stack for all temporary registers.
In this case, it is unnecessary to move data around and it is only necessary
to change the stack pointer when subroutines are entered and left.  However,
this technique uses up the indexing capabilities of some machines which
may be wanted for other purposes.

	Recursive programs can be written in any programming language by
explicitly programming the saving and restoring.  However, some languages,
e.g. FORTRAN, use termporary registers not addressable in the language so
he can't arrange for their saving and restoration and must limit himself to
programs not using such registers.  In FORTRAN this means giving up the
FORTRAN subroutine mechanism and giving up DO statements.

	The first language to use recursive subroutines on a regular basis
were the IPL languages of Newell, Shaw and Simon.  Lists were used for the
stack and the saving and restoring was done explicitly by the programmer.

	The first language provide an automatic mechanism for recursion
was LISP.

	Algol 60 and its successors allow recursion.

	Many computers have special instruction for handling stacks, e.g.
the PUSH and POP instructions of the Digital Equipment PDP-10.  Other
machines such as the Burroughs 6500 have instructions that use a hardware
stack directly.  These special facilities give a modest increase in the
efficiency of recursive programming.\.


Recursive conditional expressions

\J	The recursive use of conditional expressions provides an economical
way of getting the functions that are computable in terms of a collection
of base functions.  This technique is the basis of the LISP programming
language and also of the theoretical system of D. Scott for studying
the properties of computer programs.\.

	A conditional expression has the form, in Algol notation, of


        \F3if \F1p \F3then \F1a \F3else \F1b\F0.

\JIt is evaluated by first evaluating the propositional expression \F1p\F0.
If \F1p\F0 is \F3true\F0, the value of the conditional expression is that of
\F1a\F0, and if the value of \F1p\F0 is \F3false\F0, the value of the conditional
expression is that of \F1b\F0.  It is important to note that only
one of \F1a\F0 or \F1b\F0 is actually evaluated.

	A simple example of the use of conditional expressions is to define
the absolute value of a number by\.

	\F1|x| = \F3if\F1 x < 0 \F3then\F1 -x \F3else\F1 x.\F0

\J	Conditional expressions are used to define functions recursively
by writing the definition in the form\.

       	\F1f(x , . . . , z) ← \F4E\F1{x , . . . , z, f , g , . . . , h}\F0,

\Jwhere \F4E\F0 is an expression involving the variables,\F1x , . . . , z\F0,
the function \F1f\F0 being defined, and known or previously defined
functions \F1g , . . . , h\F0.

	An example of such a definition is\.

	\F1n! ← \F3if\F1 n = 0 \F3then\F1 1 \F3else\F1 n.(n-1)!\F0.

\J	The general method for evaluating recursive conditional expressions
is illustrated by using the above definition to evaluate 3!.  Namely,
we have\.

        3! = \F3if\F1 3=0 \F3then \F11 \F3else \F13.(3-1)!
       	   = 3.2! =3.(\F3if\F1 2=0 \F3then \F11 \F3else \F12.(2-1)!)
	   = 3.2.(\F3if \F11=0 \F3then \F11 \F3else \F11.(1-1)!)
	   = 3.2.1.(\F3if \F10=0 \F3then \F11 \F3else \F10.(0-1)!)
	   = 3.2.1.1 = 6.\F0

\JNote that the rule for evaluating conditional expressions ensures that
(-1)! is never evaluated.  This is necessary since its evaluation
wouldn't terminate.  Several points should be noted.

	First, in a programming language that uses recursive conditional
expressions, 3! would not be evaluated by the above symbolic manipulation.
Either \F1(a)\F0 would be compiled into a recursive subroutine (i.e. a subroutine
of the type explained above that calls itself and uses a stack to save
intermediate results and return addresses) or a recursive interpreter would
interpret a list structure version of \F1(a)\F0.

	Second, \F1(a)\F0 can easily be replaced by another expression for the
factorial that can be compiled into a non-recursive program.  Namely, we
write\.

	\F1n! ← fact(n, 0, 1)\F0

where

	\F1fact(n, m, p) ← \F3if\F1 m = n \F3then \F1p \F3else \F1fact(n, m+1,(m+1)p).

\J(b) \F0can be translated into a non-recursive program, because the only
occurrence of fact on the right hand side of the definition is at the
outer level, i.e. \F1fact(n, m+1,(m+1)p)\F0 gives the value of \F1fact(n, m, p) \F0in
contrast to the the situation in \F1(a) \F0where \F1(n-1)! \F0must be multiplied by
\F1n \F0to give \F1n!.  \F0This allows the object program to contain an ordinary
jump to itself rather than a subroutine call.  When this is possible,
the function definition is called iterative.  Thus fact is iterative
while the \F1(a) \F0is not.  Recursive definitions cannot in general be
replaced by iterative definitions except by encoding the stack as a
variable in the program, and if this has to be done there is no
advantage in the replacement.

	Third, there may be several occurrences of the function being
defined on the right hand side of the recursive definition, and whether
the evaluation terminates may depend on which occurrence is evaluated
first.  The following example due to Morris shows this:\.

	\F1f(x,y) ← \F3if \F1x=0 \F3then \F10 \F3else \F1f(x-1 , f(y-2, x)).\F0

\JThe reader should evaluate \F1f(2,1)\F0 to convince himself of this.  J. M.
Cadiou has given rules that give the "least fixed point"  of the 
definition regarded as a functional equation.

	It is also possible to use recursive conditional expressions
to define functions that take functions as arguments or give functions
as results.  However, there remain unsolved problems in getting
compiling algorithms that give efficient object code and give the "right"
answers in all cases.\.